すごいコンピュータ達 |

(1)

.

...

情報知能工学総論

組合せ爆発と計算

田村直之

神戸大学情報基盤センター・情報知能工学科

2013年5月29日

(2)

計算機の進歩計算機の限界組合せ爆発への挑戦まとめ

..

すごいコンピュータ達

—計算機の進歩— .

...

京コンピュータ電王戦

IBM Watson

(3)

..

^{京コンピュータ}

.

...

神戸のポートアイランドに設置されている．^{. Web}^.

10ペタFLOPSの計算速度を世界で初めて突破した．

1ペタ= 10¹⁵

FLOPS (FLoating-point Operation Per Second) 全体で864ラックから構成されている．

1ラック中の計算ノード数(CPU数)は102

(4)

..

^電王戦

第2戦参加のPonanzaソフトの画面 ^{. Web}^.

.

...

2013年，プロ棋士5人とコンピュータ5ソフトで将棋の団体戦が行われ，プロ棋士の1勝3敗1分の結果になった．

第5戦のGPS将棋は東京大学で開発され，667台のiMacを使用した．

(5)

.. IBM Watson

.

...

2011年2月16日IBMが4年間をかけて研究開発した

Watsonが，米国の人気クイズ番組Jeopardyで歴代最強チャ

ンピオン2人と対戦し優勝した．^{. Web}^.

..ビデオを見てみよう^{. YouTube}^.

2880個のPOWER7プロセッサ・コアを使用し，処理性能は

約80テラFLOPS (1テラ= 10¹²)

(6)

..

コンピュータは何でもできる

?

—計算機の限界— .

...

速度の限界フカシギの数え方計算困難な問題組合せ爆発計算量理論合体数独に挑戦

(7)

..

コンピュータはどんどん高速になっている

.

...

ムーアの法則: 「集積回路上のトランジスタ数は18か月ごとに倍になる」

トランジスタ数に比例して速度も向上している．

コンピュータは，これからも限りなく速くなるように見える．

(8)

..

これからもどんどん高速になるのか

?

.ムーアの法則は，今後も成り立つのか? ..

...

現在の回路は，すでに原子20個分程度の幅しかない．

原子数個程度の幅になれば，量子力学の不確定性原理に支配される状況になる．

物理学者のミチオ・カク博士は10年程度で限界に達すると述べている．

. ...

量子コンピュータなどの新しい技術でどうにかなるのか? いつかは，どんな問題でも解けるようになるのか?

(9)

..

これからもどんどん高速になるのか

?

.ムーアの法則は，今後も成り立つのか? ..

...

現在の回路は，すでに原子20個分程度の幅しかない．

原子数個程度の幅になれば，量子力学の不確定性原理に支配される状況になる．

物理学者のミチオ・カク博士は10年程度で限界に達すると述べている．

. ...

量子コンピュータなどの新しい技術でどうにかなるのか? いつかは，どんな問題でも解けるようになるのか?

(10)

..

^{フカシギの数え方}

.フカシギの数え方 ..

...

『フカシギの数え方』の ^.^.^ビデオを見てみよう^{. YouTube}^. 北海道大学湊離散構造処理系プロジェクト作成

.

...

原理的には計算できるが，実際には計算できそうにない計算困難な問題が存在していることが分かる．

どんな問題が，計算困難なのか?

(11)

..

^{フカシギの数え方}

.フカシギの数え方 ..

...

『フカシギの数え方』の ^.^.^ビデオを見てみよう^{. YouTube}^. 北海道大学湊離散構造処理系プロジェクト作成 .

...

原理的には計算できるが，実際には計算できそうにない計算困難な問題が存在していることが分かる．

どんな問題が，計算困難なのか?

(12)

..

簡単な問題と困難な問題

.オイラー閉路とハミルトン閉路 ..

...

配布プリントを参照し，上のグラフ(Herschelグラフ)について考えてみよう．

. ..

1 オイラー閉路は存在するか?

すべての辺をちょうど一度ずつ通る閉路 .

2.. ハミルトン閉路は存在するか?

すべての頂点をちょうど一度ずつ通る閉路

(13)

..

簡単な問題と困難な問題

.

...

連結グラフについて，

. ..

1 オイラー閉路が存在するかどうかは簡単に分かる．

奇次数の頂点が存在しないことが必要十分条件である．

. ..

2 ハミルトン閉路が存在するかどうかは難しい．

しらみつぶしに調べる方法しか知られていない．

.多項式時間と指数時間 ..

... .

1.. オイラー閉路は頂点数 n の多項式時間で求まる．多項式時間: たとえばn²や n¹⁰ に比例する時間 .

2.. ハミルトン閉路は n の指数時間が必要な方法しか知られていない．

指数時間: たとえば2ⁿ やn!に比例する時間

多項式時間で解ける問題は簡単，指数時間が必要な問題は困難と見なされる．

(14)

..

簡単な問題と困難な問題

.

...

連結グラフについて，

. ..

1 オイラー閉路が存在するかどうかは簡単に分かる．

奇次数の頂点が存在しないことが必要十分条件である．

. ..

2 ハミルトン閉路が存在するかどうかは難しい．

しらみつぶしに調べる方法しか知られていない．

.多項式時間と指数時間 ..

...

.

1.. オイラー閉路は頂点数 n の多項式時間で求まる．

多項式時間: たとえばn²や n¹⁰ に比例する時間 .

2.. ハミルトン閉路は n の指数時間が必要な方法しか知られていない．

指数時間: たとえば2ⁿ やn!に比例する時間

多項式時間で解ける問題は簡単，指数時間が必要な問題は困難と見なされる．

(15)

..

^{組合せ爆発}

.

...

「n¹⁰ ナノ秒」対「2ⁿ ナノ秒」

配布プリントを参照し，n= 10, 100, 200, 400でそれぞれ何秒 (あるいは何日)になるか計算してみよう．

2¹⁰∼10³, 1秒= 10⁹ナノ秒, 1日∼10⁵秒 1ナノ秒は光が30cm進む時間

n = 10 n= 100 n = 200 n = 400 n¹⁰ ナノ秒

10秒 10⁶日 10⁹日 10¹²日

2ⁿ ナノ秒

1 µ秒 10¹⁶日 10⁴⁶日 10¹⁰⁶日 .

...

10²³ (アボガドロ数)台の並列計算でも 10⁸³年かかる．単位をナノ秒ではなく，核時間(光が水素原子を横切る時間で約 10⁻¹⁸ 秒)としても10⁹ 倍しか速くならない．

(16)

..

^{組合せ爆発}

.

...

n = 10 n= 100 n = 200 n = 400 n¹⁰ ナノ秒 10秒 10⁶日 10⁹日 10¹²日

2ⁿ ナノ秒 1 µ秒 10¹⁶日 10⁴⁶日 10¹⁰⁶日

.

...

10²³ (アボガドロ数)台の並列計算でも 10⁸³年かかる．単位をナノ秒ではなく，核時間(光が水素原子を横切る時間で約 10⁻¹⁸ 秒)としても10⁹ 倍しか速くならない．

(17)

..

^{組合せ爆発}

.

...

n = 10 n= 100 n = 200 n = 400 n¹⁰ ナノ秒 10秒 10⁶日 10⁹日 10¹²日

2ⁿ ナノ秒 1 µ秒 10¹⁶日 10⁴⁶日 10¹⁰⁶日

.

...

10²³ (アボガドロ数)台の並列計算でも 10⁸³年かかる．

単位をナノ秒ではなく，核時間(光が水素原子を横切る時間で約 10⁻¹⁸ 秒)としても10⁹ 倍しか速くならない．

(18)

..

^{計算量理論}

.計算量理論 ..

...

計算の複雑さに関する理論を計算量理論という．

計算機の動作を抽象化したモデルとしてチューリング機械 (TM)を考える．

決定性TM (1 CPUの計算機)を用いて多項式時間で解く方

法がある問題は，クラスPの問題と呼ばれる．

非決定性TM (無限CPUの計算機)を用いて多項式時間で解く方法がある問題は，クラスNPの問題と呼ばれる．

明らかに P⊆NP であるが，P=NP かどうかは分かっていない．

P=NP問題は，計算機科学の最も重要な課題である．

(19)

..

^{計算量理論}

.計算量理論 ..

...

計算の複雑さに関する理論を計算量理論という．

計算機の動作を抽象化したモデルとしてチューリング機械 (TM)を考える．

決定性TM (1 CPUの計算機)を用いて多項式時間で解く方

法がある問題は，クラスPの問題と呼ばれる．

非決定性TM (無限CPUの計算機)を用いて多項式時間で解く方法がある問題は，クラスNPの問題と呼ばれる．

明らかに P⊆NP であるが，P=NP かどうかは分かっていない．

P=NP問題は，計算機科学の最も重要な課題である．

(20)

.. NP

_完全問題

.NP完全問題

..

...

ハミルトン閉路問題グラフ彩色問題

充足可能性判定問題(SAT) 多くのパズル

数独，カックロ，ノノグラム，ぷよぷよ，テトリス等

クラスNPに属す最も難しい問題はNP完全問題と呼ばれる．

これらを多項式時間で解くアルゴリズムは発見されていない．

多項式時間で解くアルゴリズムを考案すればチューリング賞受賞確実!

チューリング賞: 計算機科学のノーベル賞

多項式時間で解くアルゴリズムが存在しないことを証明するのでも良い．

(21)

..

^{合体数独に挑戦}

.合体数独

..

...

配布プリントの合体数独の問題を見てみよう．

タイムインターメディア社の藤原さんによる作品 http://karetta.jp/book/puzzle-generator-age ^{. Web}^. 105個の数独が合体した問題もある．

.

...

105合体数独には5000以上の白マスがある．それぞれに9通りの数字の可能性があるとすると， 9⁵⁰⁰ ∼10⁴⁷⁷ 通りを調べる必要がある．

単純なアルゴリズムでは，解くことができない．

(22)

..

^{合体数独に挑戦}

.合体数独

..

...

配布プリントの合体数独の問題を見てみよう．

タイムインターメディア社の藤原さんによる作品 http://karetta.jp/book/puzzle-generator-age ^{. Web}^. 105個の数独が合体した問題もある．

.

...

105合体数独には5000以上の白マスがある．

それぞれに9通りの数字の可能性があるとすると，

9⁵⁰⁰ ∼10⁴⁷⁷ 通りを調べる必要がある．

単純なアルゴリズムでは，解くことができない．

(23)

..

コンピュータを賢くする

—組合せ爆発への挑戦— .

...

組合せ爆発に挑戦する技術

Sugar制約ソルバー

(24)

..

組合せ爆発に挑戦する技術

.

...

計算機の発明以降，研究者らは組合せ爆発に挑戦し続けてきた．

動的計画法局所探索法

遺伝的アルゴリズム制約ソルバー

SATソルバー，BDD・ZDD

ここ10年で，制約ソルバーやSATソルバーの技術が飛躍的に発展している．

多くの実際的な問題を非常に高速に解くことができるようになった．

すべてのNP困難な問題を高速に解けるわけではない．

(25)

.. Sugar

_{制約ソルバー}

制約充足問題 SAT問題

SAT問題の解制約充足問題の解

符号化

SATソルバー

復号化

.

...

私の研究室で開発している制約ソルバー ^{. Web}^.

問題の条件を記述するだけで，ソルバーが解を探してくれる．

国際制約ソルバー競技会の複数部門で2年連続優勝．

パズルを解くのにも向いている :-)

(26)

.. Sugar

制約ソルバーでパズルを解く

.合体数独

..

...

105合体数独は5秒程度で解ける．

デモ ^{. Ans}^.

.ノノグラム(お絵かきロジック，ピクロス) ..

...

100×100のノノグラムも15秒程度で解ける．

デモ ^{. Ans}^.

ほとんどのニコリのパズルを解くことができる:-) パズルをSugar制約ソルバーで解く ^{. Web}^.

興味がある人は，ぜひ使ってみてください．

(27)

..

^まとめ

.

...

組合せ爆発計算困難な問題

ハミルトン閉路計算量理論

P=NP問題

組合せ爆発に挑戦する技術制約ソルバー

(28)

..

パズルとプログラミング

.

...

パズルを解くプログラムを書いてみよう

!

プログラミング・スキル上達に最適問題自体は単純だが，解くのが難しい．

遅いプログラムと速いプログラムで，1000倍以上の差がつくこともしばしばある．

各種のプログラミング・コンテストにもパズル的な問題が良く出てくる．

ACMプログラミング・コンテスト Project Euler

これから，賢いコンピュータが必要とされる．人間の知的活動を支援するコンピュータ解けると楽しい．

(29)

..

パズルとプログラミング

.

...

パズルを解くプログラムを書いてみよう

!

プログラミング・スキル上達に最適問題自体は単純だが，解くのが難しい．

遅いプログラムと速いプログラムで，1000倍以上の差がつくこともしばしばある．

各種のプログラミング・コンテストにもパズル的な問題が良く出てくる．

ACMプログラミング・コンテスト Project Euler

これから，賢いコンピュータが必要とされる．

人間の知的活動を支援するコンピュータ解けると楽しい．